package ljl.alg.wangzheng_camp.round1.sort;

import java.util.Random;

/**
 * 分析快选，和堆排，写吧
 * */
public class _215_kth_largest {
    
    /**
     * 不错，写对了
     * 随机数，还是得加，能快一倍多
     * */
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, k);
    }
    Random random = new Random();
    int quickSelect(int[] nums, int left, int right, int k) {
        if (left == right) return nums[left];
        if (left > right) return -1;
        int l = left, r = right;
        
        int i = random.nextInt(r - l + 1) + l;
        int t = nums[l];
        nums[l] = nums[i];
        nums[i] = t;
        
        int pivot = nums[l];
        while (l < r) {
            while (l < r && nums[r] >= pivot) r--;
            nums[l] = nums[r];
            while (l < r && nums[l] <= pivot) l++;
            nums[r] = nums[l];
        }
        nums[l] = pivot;
        if (nums.length - k == l) return pivot;
        if (nums.length - k > l) return quickSelect(nums, l + 1, right, k);
        return quickSelect(nums,left, l - 1, k);
    }
    
    /*
    * 这是一个思想，懂吗，思想！
    * 大顶堆，大顶，往最后挪；挪 k 次，就是答案
    * 当然先要建堆，建好堆后开始挪，挪一次，重新建堆
    *
    * */
    public int findKthLargest2(int[] nums, int k) {
        // 建好堆
        for (int i = nums.length / 2; i >= 0; i--) {
            percolateDown(nums, i, nums.length);
        }
        for (int i = 0; i < k - 1; i++) {
            swap(nums, 0, nums.length - i - 1);
            percolateDown2(nums, 0, nums.length - i - 1);
        }
        return nums[0];
    }
    
    // 要把 from 弄下去不是吗，找地方，干他
    // 它大小未知，比它大的要上来
    void percolateDown2(int[] nums, int from, int to) {
        int t = nums[from];
        for (int child = from * 2 + 1; child < to; child = child * 2 + 1) {
            if (child + 1 < to && nums[child + 1] > nums[child]) child++;
            if (nums[child] > t) {
                nums[from] = nums[child];
                from = child;
            } else {
                break;
            }
        }
        // 这个条件，你把我害惨了！
        nums[from] = t;
    }
    void swap(int[] nums, int l, int r) {
        if (l != r) {
            int t = nums[l]; nums[l] = nums[r]; nums[r] = t;
        }
    }
    
    public void percolateDown(int[] a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        }
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a, i, largest);
            percolateDown(a, largest, heapSize);
        }
    }
    
}
